package com.java.util;

public class InsertionSort {

    /**
     * 这里有了头节点 更简单了。
     *
     * @param array
     */
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;

            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }


    public static void insertionSort1(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int num = array[i];

            // 这个数据应该在哪个位置
            int position = -1;

            // 前面i-1个数肯定排好序的    ，由小到大
            // 一个一个地循环找位置
            for (int j = i - 1; j >= 0; j--) {
                int temp = array[j];
                if (num < temp) {
                    position = j;
                    continue;
                }
                break;
            }

            // 此数最大不需要动
            if (position == -1) {
                continue;
            }

            // 把当前的数放到找到的位置，
            // 所有的位置后移一位，把position的空让出来
            for (int k = i - 1; k >= position; k--) {
                array[k + 1] = array[k];
            }

            array[position] = num;
        }
    }


    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        insertionSort(array);
        System.out.println("Sorted array: ");
        for (int i : array) {
            System.out.print(i + " ");
        }

        System.out.println(">>>>>>>>>>>>>>>>>>>>>");
        // 查找12所在的位置
        System.out.println(binarySearch(array, 1));
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            }
            else if (target < arr[mid]) {
                right = mid - 1;

            } else if (target > arr[mid]) {
                left = mid + 1;
            }
            else {

            }

        }
        return -1;

    }

}
